/**
 * \* Created with IntelliJ IDEA.
 * \* User: Administrator
 * \* Date: 2021/11/3
 * \* Time: 15:35
 * \* To change this template use File | Settings | File Templates.
 * \* Description:
 * \
 */

//ListNode代表一个节点
class ListNode{
    public int val;//代表一个整数
    public ListNode next;//存储的是节点的地址，类型是ListNode

    public ListNode(int val){
        this.val=val;
    }
}
public class MyLinkedList {

    public ListNode head;//链表的投引用
    //不定义在上面的原因——head是链表的头，不是节点的头，节点只有两个属性一个属性是val值，一个属性是next值


//    public static void main(String[] args) {
//        ListNode listNode=new ListNode(1);
//    }
    public void  createList(){
        ListNode listNode1=new ListNode(12);
        ListNode listNode2=new ListNode(23);
        ListNode listNode3=new ListNode(34);
        ListNode listNode4=new ListNode(45);
        ListNode listNode5=new ListNode(56);

        listNode1.next=listNode2;
        listNode2.next=listNode3;
        listNode3.next=listNode4;
        listNode4.next=listNode5;
        this.head=listNode1;

    }

    public void display(){
        //如果是this.head.next  会少打印一个
        ListNode cur=this.head;
        while (cur!=null){
            System.out.print(cur.val+" ");
            cur=cur.next;
        }
        System.out.println();
    }
    //头插法
         public void addFirst(int data){
            ListNode node=new ListNode(data);
            node.next=this.head;
            this.head=node;
//            if(this.head==null){
//                this.head=node;
//            }else {
//                node.next=this.head;
//                this.head=node;
//            }
       }
     //尾插法
         public void addLast(int data){
            ListNode node=new ListNode(data);
            if(this.head==null){
                this.head=node;
            }else{
                ListNode cur=this.head;
                while (cur.next!=null){
                    cur=cur.next;
                }
            }

         }
         //找到index-1位置节点的地址
         public ListNode findIndex(int index){
            ListNode cur=this.head;
             while ((index - 1 != 0)) {
                 cur=cur.next;
                 index--;
             }
             return cur;
         }
         //任意位置插入,第一个数据节点为0号下标
         public void addIndex(int index,int data){
            if(index<0||index>size()){
                System.out.println("index位置不合法！");
                return;
            }
            if(index==0){
                addFirst(data);
                return;
            }
            if(index==size()){
                addLast(data);
                return;
            }
            ListNode cur= findIndex(index);
            ListNode node=new ListNode(data);
            node.next=cur.next;
            cur.next=node;
         }
//查找是否包含关键字key是否在单链表当中
         public boolean contains(int key){
            ListNode cur=this.head;
            while (cur!=null){
                if (cur.val==key){
                    return true;
                }
                cur=cur.next;
            }
            return false;
         }
         //找到要删除的关键字的前驱
         public ListNode searchPerv(int key){
        ListNode cur=this.head;
        while (cur.next!=null){
            if(cur.next.val==key){
                return cur;
            }
            cur=cur.next;
        }
        return null;
    }
 //删除第一次出现关键字为key的节点
         public void remove(int key){
            if (this.head==null){
                System.out.println("单链表为空，不能伤处！");
                return;
            }
            if(this.head.val==key){
                this.head=this.head.next;
                return;
            }
            ListNode cur=searchPerv(key);
            if (cur ==null){
                System.out.println("没有你要删除的节点");
                return;
            }
            ListNode del = cur.next;
            cur.next=del.next;
         }
 //删除所有值为key的节点
 public ListNode removeAllKey(int key){
        if (this.head==null)return null;
            ListNode prev=this.head;
            ListNode cur=this.head.next;

            while (cur!=null){
                if (cur.val==key){
                    prev.next=cur.next;
                    cur=cur.next;
                }else {
                    prev=cur;
                    cur=cur.next;
                }
            }
            //最后处理头
            if(this.head.val==key){
                this.head=this.head.next;
            }
            return this.head;
    }
 //得到单链表的长度
         public int size(){
            int count=0;
            ListNode cur=this.head;
            while (cur!=null){
                count++;
                cur=cur.next;
            }
            return count;
         }
         public void clear(){
            while (this.head==head.next){
                ListNode curNext=head.next;
                this.head.next=null;
                this.head=curNext;

            }
         }
}
